package com.daybyday.day1;


import cn.Leecode.Soution;
import com.interview.javabasic.JUC.A;
import sun.reflect.generics.tree.Tree;

import java.util.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2020/10/14

*/

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }
}
public class Solution {

    List<int[]> freq = new ArrayList<int[]>();
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();
    ReentrantLock lock = new ReentrantLock();
    Condition con = lock.newCondition();

    public static void main(String[] args) {
        Solution S = new Solution();
    }

    private TreeNode pre = null;
    private TreeNode head = null;

    public TreeNode Convert(TreeNode root) {
        inOrder(root);
        return head;
    }


    private void inOrder(TreeNode node) {
        if (node == null)
            return;
        inOrder(node.left);
        node.left = pre;
        if (pre != null)
            pre.right = node;
        pre = node;
        if (head == null)
            head = node;
        inOrder(node.right);
    }


    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null || pHead.next == null){
            return pHead;
        }
        ListNode next = pHead.next;
        if(pHead.val == next.val){
            while(next != null && pHead.val == next.val){
                next = next.next;
            }
            return deleteDuplication(next);
        }else{
            pHead.next = deleteDuplication(pHead.next);
        }
        return pHead;
    }


    public int[] exchange(int[] nums) {
        int size = nums.length - 1;
        int j = size;
        int i = 0;
        while(i < size && i <= j){
            if((nums[i] & 1) == 0){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j--;
            }else{
                i++;
            }
        }
        return nums;
    }

    public boolean isNumber(String s) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i <= 9; i++) {
            list.add(i + "");
        }
        boolean hasE = false;
        boolean hasPoint = false;
        boolean hasFlag = false;
        if (s.charAt(0) == '+' || s.charAt(0) == '-') {
            hasFlag = true;
        }
        char c = s.charAt(0);
        list.add("+");list.add("-");list.add("e");list.add("E");list.add(".");
        if ((!list.contains(s.charAt(0) + "")) || s.charAt(0) == 'E' || s.charAt(0)=='e'){
            return false;
        }
        for (int i = 1; i < s.length(); i++) {
            if (!list.contains(s.charAt(i) + "")) return false;
            if (s.charAt(i) == '.'){
                if (!hasPoint){
                    hasPoint = true;
                    if (hasE){
                        return false;
                    }
                }else{
                    return false;
                }
            }else if (s.charAt(i) == 'e' || s.charAt(i) == 'E'){
                if (Integer.parseInt(s.substring(0,i))> 10) return false;
                if (!hasE){
                    hasE = true;
                }else{
                    return false;
                }
            }else if (s.charAt(i) == '+' || s.charAt(i) == '-'){
                if (!(s.charAt(i-1) == 'e' || s.charAt(i - 1) == 'E')){
                    return false;
                }
            }
        }

        return true;
    }

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

    public boolean exist(char[][] board, String word) {
        for(int i = 0;i < board.length;i++){
            for(int j = 0 ; j < board[0].length;j ++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;

    }

    public boolean dfs(char[][] board,String word,int i,int j,int pos){
        if(i < 0 || j < 0|| j >= board[0].length || i >= board.length ||board[i][j] != word.charAt(pos)) return false;
        if(pos == word.length() - 1) return true;
        board[i][j] = ' ';
        boolean res = dfs(board,word,i,j + 1, pos + 1) || dfs(board,word,i,j - 1,pos + 1)
                || dfs(board,word,i - 1,j,pos + 1) || dfs(board,word,i + 1, j, pos + 1);
        board[i][j] = word.charAt(pos);
        return res;
    }

    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点

        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_left]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_left]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }


    public boolean findNumberIn2DArray(int[][] matrix, int target) {
            int pos = matrix[0].length - 1;
        int layer = 0;
        while(pos >=0 && layer < matrix.length){
            if(matrix[layer][pos] >target){
                pos--;
            }
            else if(matrix[layer][pos] < target){
                layer++;
            }

            else if(matrix[layer][pos] == target){
                return true;
            }
        }
        return false;
    }

    public boolean canMeasureWater(int x, int y, int z) {
        if(x + y < z) return false;
        if (x == 0 || y == 0) return z == 0 || x + y == z;

        return z % gcd(x,y) == 0;
    }

    public int gcd(int x,int y){
        int res = x % y;
        while (res != 0){
            x = y;
            y = res;
            res =  x % y;
        }
        return y;
    }

    ArrayList<Integer>[] graph;
    int[] res;
    int[] quiet;

    public String fractionToDecimal(int numerator, int denominator) {
        long before = Math.abs((long) numerator / (long) denominator);
        long after = Math.abs((long) numerator % (long) denominator);
        StringBuilder sb = new StringBuilder();
        if ((numerator < 0 && denominator > 0)|| (numerator > 0 && denominator < 0)){
            sb.append("-");
        }
        Map<Long,Integer> map = new HashMap<>();
        if (after == 0){
            return sb.toString();
        }

        sb.append(before);sb.append(".");
        while (after != 0){
            if (map.containsKey(after)){
                sb.insert(map.get(after),"(");
                sb.append(")");
                break;
            }
            map.put(after,sb.length());
            after *= 10;
            sb.append(String.valueOf(after / Math.abs((long)denominator)));
            after %= Math.abs((long)denominator);
        }
        return sb.toString();
    }

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        this.quiet = quiet;
        int n = quiet.length;
        graph = new ArrayList[n];
        res = new int[quiet.length];
        Arrays.fill(res,-1);
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < richer.length; i++) {
            graph[richer[i][1]].add(richer[i][0]);
        }

        for (int i = 0; i < n; i++) {
            dfs(i);
        }
        return res;
    }

    public int dfs(int node) {
        if (res[node] == -1) {
            res[node] = node;
            for (int child: graph[node]) {
                int cand = dfs(child);
                if (res[cand] < quiet[res[node]])
                    res[node] = cand;
            }
        }
        return res[node];
    }

    public boolean carPooling(int[][] trips, int capacity){
        Arrays.sort(trips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        Map<Integer,Integer> map = new TreeMap<>();
        int peopleCount = 0;
        if (peopleCount > capacity) return false;
        int place = 0;
        for (int[] trip : trips) {
            if (trip[0] > capacity) return false;

            for (Integer integer : map.keySet()) {
                if (integer <= trip[1] && integer > place){
                    peopleCount -= map.get(integer);
                    place = integer;
                }
            }
            if (map.containsKey(trip[2])){
                map.put(trip[2],map.get(trip[2]) + trip[0]);
            }else {
                map.put(trip[2],trip[0]);
            }
            peopleCount += trip[0];
            if (peopleCount > capacity) return false;
        }
        return true;
    }

    public int[] constructArr(int[] a) {
        int n = a.length;
        int[] res = new int[a.length];
        for (int i = 0; i < n; i++) {

        }
        return res;
    }

    public int bagOfTokensScore(int[] tokens, int P) {
        Arrays.sort(tokens);
        int left = 0;
        int right = tokens.length - 1;
        int max = 0;
        int score = 0;
        while (P >= 0 && left <= right){
            max = Math.max(score,max);
            if (P >= tokens[left]){
                P -= tokens[left];
                left++;
                score++;
            }else if (score > 0){
                P += tokens[right];
                right -- ;
                score --;
            }else{
                right -- ;
            }
            max = Math.max(score,max);
        }
        return max;
    }

    public int smallestDifference(int[] a, int[] b) {
        int s = -2147483648;
        Arrays.sort(a);
        Arrays.sort(b);
        int i = 0, j = 0;
        int res = Integer.MAX_VALUE;
        while (i < a.length && j < b.length){
            res = Math.min(res,(int)Math.abs((double)a[i] - (double)b[j]));
            if (a[i] <= b[j]){
                i++;
            }else{
                j++;
            }
        }
        return res;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean res = false;

        return res;
    }

    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Map<Character,Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int left = 0,right = 0; right <chars.length ; right++) {
            Integer pos = map.get(chars[right]);
            if(map.keySet().contains(chars[right])){
                left = pos + 1;
                sb = new StringBuilder(s.substring(left,right));
            }
            map.put(chars[right],right);
             sb.append(chars[right]);
            res = Math.max(res,right - left + 1);
        }
        return res;

    }

    public ListNode deleteDuplicates(ListNode head) {
        PriorityQueue<Integer> que = new PriorityQueue<>();
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode tmp = head;
        ListNode cur = tmp.next;
        while(tmp != null && cur!=null){
            if(tmp.val == cur.val){
                tmp.next = cur.next;
                cur.next = null;
                cur = tmp.next;
                continue;
            }
            tmp = tmp.next;
            cur = cur.next;
        }
        return node.next;
    }

    public int equalSubstring(String s, String t, int maxCost) {
        int res = 0;
        if(s.length() != t.length()) return res;
        int[] minus = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            minus[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        for (int i = 0; i < minus.length; i++) {
            int tmp = maxCost;
            for (int j = i ; j <minus.length; j++) {
                tmp -= minus[j];
                if (tmp < 0) {
                    res = Math.max(res,j - i );
                    break;
                }
            }
            if (tmp >= 0) res = Math.max(minus.length - i,res);
        }
        return res;
    }

    public boolean queryString(String S, int N) {
        for (int i = 0; i < N + 1; i++) {
            String s = Integer.toBinaryString(i);
            if (!S.contains(s)) return false;
        }
        return true;
    }

    public int countVowelStrings(int n) {
        int[][] dp = new int[n + 1][5];

        for (int i = 0; i < 5; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
            dp[i][2] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
            dp[i][3] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3];
            dp[i][4] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4];
        }

        return dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4];
    }


    public String replaceWords(List<String> dictionary, String sentence) {

        String[] s = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        Collections.sort(dictionary, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        boolean flag = false;
        for (String s1 : s) {
            for (String s2 : dictionary) {
                if (s1.startsWith(s2)){
                    sb.append(s2);
                    sb.append(" ");
                    flag = true;
                    break;
                }
            }
            if (!flag){
                sb.append(s1);
                sb.append(" ");
            }
            flag = false;
        }
        return sb.toString().trim();
    }

    public String longestWord(String[] words) {
        String res = "";
        int n = words.length;
        Arrays.sort(words);
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        List<String> all = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            all.add(words[i]);
        }
        for (int i = all.size() - 1; i > 0 ; i --) {
            for (int j = 0; j < i; j++) {
                if (all.get(i).contains(all.get(j))){
                    String replace = all.get(i).replace(all.get(j),"");
                    if (all.contains(replace) || "".equals(replace) ||replace == null){
                        res = res.length() > all.get(i).length() ? res : all.get(i);
                    }
                }
            }
        }
        return res;
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0 || intervals[0].length == 0){
            int[][] res = new int[1][2];
            res[0][0] = newInterval[0];
            res[0][1] = newInterval[1];
            return res;
        }
        int left = -1,right = -1;
        int leftVal = 0,rightVal = 0;
        boolean leftflag = false,rightflag = false;
        for (int i = 0; i < intervals.length; i++) {
            if (!leftflag){
                if (newInterval[0]>= intervals[i][0]&& newInterval[0] <= intervals[i][1]){
                    left = i + 1;
                    leftVal = intervals[i][0];
                    leftflag = true;
                }else if (newInterval[0] < intervals[i][0]){
                    left = i + 1;
                    leftVal = newInterval[0];
                    leftflag = true;
                }
            }
            if (!rightflag){
                if (newInterval[1] >= intervals[i][0] &&  newInterval[1] <= intervals[i][1]){
                    right = i + 1;
                    rightVal = intervals[i][1];
                    rightflag = true;
                }else if (newInterval[1] < intervals[i][0]){
                    right = i;
                    rightVal = newInterval[1];
                    rightflag = true;
                }
            }

        }
        if (right < 0){
            right = intervals.length;
            rightVal = newInterval[1];
        }
        if (left < 0){
            left = intervals.length + 1;
            leftVal = newInterval[0];
        }
        int[][] res =  new int[intervals.length - right + left][2];
        int i;
        for ( i = 0; i < left - 1; i++) {
            res[i][0] = intervals[i][0];
            res[i][1] = intervals[i][1];
        }
        res[i][0] = leftVal;
        res[i++][1] = rightVal;
        for(; i < res.length; i++){
            res[i][0] = intervals[right][0];
            res[i][1] = intervals[right++][1];
        }
        return res;
    }

    public List<Integer> pathInZigZagTree(int label) {
        Set<Integer> res = new TreeSet<>();
        res.add(label);
        int layer = (int)(Math.log(label) / Math.log(2));
        while (label != 1){
            int size =  (int)Math.pow(2,layer - 1);
            int begin = (int)Math.pow(2,layer - 1);
            int end = begin + size - 1;
            int mid = (end + begin) / 2;
            if(label / 2 > mid){
                label = begin + end - label / 2 ;

            }else{
                label = end - (label / 2 - begin);
            }
            res.add(label);
            layer--;
        }
        return new ArrayList<>(res);
    }

     public ListNode swapNodes(ListNode head, int k) {
        ListNode tmp = head;
        int len = 0;
        while (tmp != null){
            tmp = tmp.next;
            len ++ ;
        }
        ListNode leftNode = null;
        ListNode rightNode = null;
        tmp = head;
        int left = 0,right = 0;
        for (int i = 1; i <= k || i <= len - k+1; i++) {
            if (i == k) {
                left = tmp.val;
                leftNode = tmp;
            }
            if (i == len - k + 1) {
                right = tmp.val;
                rightNode = tmp;

            }
            tmp = tmp.next;
        }
        leftNode.val = right;
        rightNode.val = left;
        return head;
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }

}

